package leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * 描述:19. 删除链表的倒数第 N 个结点
 *
 * @author Madison You
 * @created 23:53
 */
public class Mid_19_RemoveNthFromEnd {

    public static void main(String[] args) {
        int[] ints = {1,2,3,4,5};
        ListNode node = Mid_2_AddTwoNumbers.createNode(ints);
        ListNode listNode = removeNthFromEnd1(node, 2);
        System.out.println(listNode);
    }

    public static ListNode removeNthFromEnd(ListNode head, int n) {
        ArrayList<Integer> arrayList = new ArrayList<>();
        while (head != null) {
            arrayList.add(head.val);
            head = head.next;
        }
        arrayList.remove(arrayList.size() - n);
        if (arrayList.isEmpty()) {
            return null;
        }
        ListNode listNode = new ListNode(arrayList.get(0));
        ListNode other = listNode;
        for (int i = 1; i < arrayList.size(); i++) {
            ListNode node = new ListNode(arrayList.get(i));
            other.next = node;
            other = other.next;
        }
        return listNode;
    }

    public static ListNode removeNthFromEnd1(ListNode head, int n) {
        // 双指针的思想
        // 定义一个快指针,定义一个慢指针
        ListNode slow = head;
        ListNode fast = head;
        // 先让快指针走n步
        while(n--!=0){
            fast=fast.next;
        }
        // 如果快指针走到了最后说明删除的是第一个节点,就返回head.next就好
        if(fast==null){
            return head.next;
        }
        // 使得slow每次都是在待删除的前一个节点, 所以要先让fast先走一步
        fast=fast.next;
        while(fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        // 因为已经保证了是待删除节点的前一个节点, 直接删除即可
        slow.next=slow.next.next;
        return head;
    }


}
